// 删除链表的倒数第N个节点
public class RemoveNthFromEnd {

  /**
   * 第一种方法：双指针法
   * 定义两个快慢指针
   * 快指针要比慢指针快n个节点，这样慢指针最后就能指向倒数第n个节点
   */
  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummyhead = new ListNode(0);
    dummyhead.next = head;
    // 定义快慢指针
    ListNode fastIndex = dummyhead;
    ListNode slowIndex = dummyhead;
    for (int i = 0; i <= n; i++) {
      fastIndex = fastIndex.next;
    }
    while (fastIndex != null) {
      fastIndex = fastIndex.next;
      slowIndex = slowIndex.next;
    }

    if (slowIndex.next != null) {
      slowIndex.next = slowIndex.next.next;
    }
    return dummyhead.next;
  }

  // 定义一个指针的节点
  class ListNode {
    // 节点的值
    int val;
    // 下一个节点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {

    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
      this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }
}
